//
//  main.c
//  C_Study
//
//  Created by rui on 12-6-30.
//  Copyright (c) 2012年 Wang Rui. All rights reserved.
//

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <assert.h>
#include <unistd.h> 

/*
 @要点：动态链栈
 */

typedef unsigned int bool;
#define true 1;
#define false 0;

#undef DEBUG
#define DEBUG 1

typedef struct Node {
	struct Node *pNext;
	int data;
}NODE,*PNODE;


typedef struct Stack {
	PNODE pTop;
	PNODE pBottom;
}STACK, *PSTACK;

void init(PSTACK pSt){
	assert(pSt != NULL);
	pSt->pTop = (PNODE)malloc(sizeof(NODE));
	if (pSt->pTop == NULL) {
		exit(-1);
	}
	
	pSt->pTop->pNext = NULL;
	pSt->pBottom = pSt->pTop;
}

bool is_empty(PSTACK pSt){
	assert(pSt != NULL);
	return (pSt->pBottom == pSt->pTop);
}

void push(PSTACK pSt,int val){
	assert(pSt != NULL);
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	if (NULL == pNew) {
		exit(-1);
	}
	pNew->pNext = pSt->pTop;//新节点指向前一个节点
	pNew->data = val;
	pSt->pTop = pNew;
}

bool pop(PSTACK pSt,int *popVal){
	assert(pSt != NULL);
	if (is_empty(pSt)) {
		return false;
	}
	
	PNODE p = pSt->pTop;
	*popVal = p->data;
	pSt->pTop = p->pNext;
	free(p);
	p = NULL;
	
	return true;
}

void travel_stack(PSTACK pSt){
	assert(pSt != NULL);
	PNODE p = pSt->pTop;
	while (p != pSt->pBottom) {
		printf("%d ",p->data);
		p = p->pNext;
	}
	printf("\n");
}

//销毁栈
void clear(PSTACK pSt){
	assert(pSt != NULL);
	
	PNODE p = pSt->pTop;
	PNODE q = NULL;
	
	while (p != pSt->pBottom) {
		q = p->pNext;
		free(p);
		p = q;
	}
	
	pSt->pTop = pSt->pBottom;
}

/**********************************
 *@ main函数
 **********************************/
int main(int argc, const char * argv[])
{
	int val;
	
	STACK S;
	init(&S);
	
	push(&S,2);
	push(&S,5);
	push(&S,7);
	push(&S,9);
	push(&S,5);
	travel_stack(&S);
	
	pop(&S,&val);
	travel_stack(&S);
	
	clear(&S);
	travel_stack(&S);
	
	return 0;
}

